The present invention generally relates to the field of electronic computer systems, and more particularly, to a method of maintaining the contiguity of files stored on magnetic disks and positioning those files in a manner that reduces the average seek time for read and write accesses to the disk. Although this method was developed for mass storage peripherals connected to Digital Equipment Corporation VAX.RTM. computers running the VMS.RTM. operating system, the method is not limited in this respect and is broadly applicable to mass storage devices on other hardware platforms. VAX and VMS are registered trademarks of Digital Equipment Corporation.
In the course of normal data processing operations, data, in the form of files, are created and deleted on magnetic disk media. Generally, the operating system of the computer attempts to create new files contiguously on the disk. However, as the disk fills and less free space is available, it becomes highly likely that the contiguity of files cannot be maintained. When this happens, the operating system will search for the largest pieces of available free space and will allocate space in this sequence until the entire file is created. The net result is that files become fragmented. i.e., in several "pieces" on the disk. Conversely, as files are deleted, it creates more "holes" of free space. As contiguous free space deteriorates, the problem of contiguous file creation is exacerbated.
File fragmentation is undesirable. Under the VMS operating system each disk contains an index file designated INDEXF.SYS that specifies the location of all files on the disk. When a file is to be accessed, an initial access is made to the appropriate block (512 character aggregate of disk space) in the index file. This block tells the operating system the address of the target file. If the target file is fragmented, the heads on the disk will have to make multiple accesses (I/O's) to read the entire file. In cases of extreme fragmentation, another access must be made to the index file to get the addresses for additional pieces of the file. This is called a "window turn" and requires significant CPU resources as well as multiple I/O's. As I/O's increase and window turns utilize CPU cycles, overall performance on the system is degraded, resulting in I/O bottlenecks, reduced productivity, and a deterioration of terminal response time for interactive users.
VMS systems offer one solution to the file fragmentation problem. This solution entails doing an indexed backup to tape of the entire disk, re-initializing the disk, and restoring the disk from the tape. This will be referred to below as the backup model. As FIG. 6 illustrates, all of the free space lands at the back-(high logical block number (LBN)) end of the disk. As files are created and deleted, the disk quickly degenerates to its former state. The defragmentation of the disk using tape backups is labor-intensive and time consuming, taking up to four hours for a 456Mb disk.
Many commercial products attempt to address and overcome the problem of file fragmentation. One such product is PC Tools Deluxe.TM. by Central Point Software, Inc. The software package includes a feature which arranges the files on a hard disk or diskette such that each file is contained in one contiguous area. Another feature unfragments files and moves free space to the back of the disk. The software also permits files to be arranged in a predetermined manner on the hard disk. For example, all files for a given subdirectory may be kept together to keep data and program overlay files adjacent one another. This reduces the amount of disk head movement needed. A directory sort feature permits the files within directories to be sorted by file name, file time, file extension, or file size. Information regarding these features may be found in PC Tools Deluxe, Version 5, December 1988. However, this and similar produces arrange free space at the back of the disk. As described above, as files are created and deleted, contiguous free space deteriorates and the fragmentation problems return.
The above techniques may be illustrated as in FIG. 1. FIG. 1 illustrates a disk having a plurality of files (designated H in the Figure) and free space (designated F) arranged as shown. If a new file is created, it may be necessary to write the file to two or more non-contiguous blocks of free user space, resulting in file fragmentation. File fragments FR1, FR2, and FR3 represent a file written to three non-contiguous blocks of free space. The heads on the disk will have to access each of the fragments FR1, FR2, and FR3, resulting in degraded system performance. The above-described systems for unfragmenting files will result in disk arranged as illustrated in FIG. 2. However, as files are deleted and written to the free space, fragmentation again occurs and system performance is degraded.